#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>



/*****定义结构体*****/
struct btnode
{
    int data;
    struct btnode *lc, *rc;
}; //*btnode, *btree;
typedef struct btnode btnode;
typedef struct btnode *btree;
/*****定义结构体*****/



/******核心功能函数*****/
int btree_height(btree t)
{
    int h = 0;
    if (t == NULL)
    {
        return h;
    }
    else
    {
        if (btree_height(t->lc) > btree_height(t->rc))
        {
            h = btree_height(t->lc) + 1;
        }
        else
        {
            h = btree_height(t->rc) + 1;
        }
        return h;
    }
}
/******核心功能函数*****/


/*****声明二叉树结点*****/
btree t0, t1, t2, t3, t4, t5, t6, t7, t8, t9;
/*****声明二叉树结点*****/



/*****初始化二叉树*****/
void t_init()
{
    t1->data = 1;
    t2->data = 2;
    t3->data = 3;
    t4->data = 4;
    t5->data = 5;
    t6->data = 6;
    t7->data = 7;
    t8->data = 8;
    t1->lc = NULL;
    t1->rc = NULL;
    t2->lc = NULL;
    t2->rc = NULL;
    t3->lc = NULL;
    t3->rc = NULL;
    t4->lc = NULL;
    t4->rc = NULL;
    t5->lc = NULL;
    t5->rc = NULL;
    t6->lc = NULL;
    t6->rc = NULL;
    t7->lc = NULL;
    t7->rc = NULL;
    t8->lc = NULL;
    t8->rc = NULL;
}
/*****初始化二叉树*****/



/***输出孩子结点的数据域***/
void print_t(btree t)
{
    if (t != NULL)
    {
        printf("当前结点为%d   ", t->data);
        if (t->lc != NULL)
        {
            printf("左结点为%d    ", t->lc->data);
        }
        else
        {
            printf("左结点为空   ");
        }
        if (t->rc != NULL)
        {
            printf("右结点为%d\n", t->rc->data);
        }
        else
        {
            printf("右结点为空\n");
        }
        if (t->lc != NULL)
        {
            print_t(t->lc);
        }
        if (t->rc != NULL)
        {
            print_t(t->rc);
        }
    }
    else
    {
        printf("二叉树为空！\n");
    }
}
/***输出孩子结点的数据域***/



/*****主函数*****/
int main()
{

    t0 = NULL;
    t1 = (btree)malloc(sizeof(btnode));
    t2 = (btree)malloc(sizeof(btnode));
    t3 = (btree)malloc(sizeof(btnode));
    t4 = (btree)malloc(sizeof(btnode));
    t5 = (btree)malloc(sizeof(btnode));
    t6 = (btree)malloc(sizeof(btnode));
    t7 = (btree)malloc(sizeof(btnode));
    t8 = (btree)malloc(sizeof(btnode));

    /***必须先初始化二叉树，否则指针域可能出现野指针***/
    t_init();
    /***必须先初始化二叉树，否则指针域可能出现野指针***/

    /***空二叉树***/
    printf("/*****空二叉树*****/\n");
    t_init();
    print_t(t0);
    printf("       空二叉树的高度：%d\n", btree_height(t0));
    printf("/*****空二叉树*****/\n\n\n\n");
    /***空二叉树***/

    /***第1棵非空二叉树***/
    printf("/*****第1棵非空二叉树*****/\n");
    t1->lc = t2;
    t1->rc = t3;
    t2->lc = t4;
    t2->rc = t5;
    t3->lc = t6;
    t3->rc = t7;
    print_t(t1);
    printf("第1棵非空二叉树的高度：%d\n", btree_height(t1));
    printf("/*****第1棵非空二叉树*****/\n\n\n\n");
    /***第1棵非空二叉树***/

    /***第2棵非空二叉树***/
    printf("/*****第2棵非空二叉树*****/\n");
    t_init();
    t1->lc = t2;
    t1->rc = t3;
    t2->lc = t4;
    t2->rc = t5;
    t3->rc = t6;
    t5->lc = t7;
    print_t(t1);
    printf("第2棵非空二叉树的高度：%d\n", btree_height(t1));
    printf("/*****第2棵非空二叉树*****/\n\n\n\n");
    /***第2棵非空二叉树***/

    /***第3棵非空二叉树***/
    printf("/*****第3棵非空二叉树*****/\n");
    t_init();
    t1->lc = t2;
    t1->rc = t3;
    t2->lc = t4;
    t4->lc = t5;
    t4->rc = t6;
    t3->rc = t7;
    print_t(t1);
    printf("第3棵非空二叉树的高度：%d\n", btree_height(t1));
    printf("/*****第3棵非空二叉树*****/\n\n\n\n");
    /***第3棵非空二叉树***/

    /***第4棵非空二叉树（与第5题的第4棵非空二叉树不同）***/
    printf("/*****第4棵非空二叉树*****/\n");
    t_init();
    t1->lc = t2;
    t1->rc = t3;
    t2->lc = t4;
    t4->lc = t5;
    t4->rc = t6;
    t3->lc = t7;
    t6->rc = t8;
    print_t(t1);
    printf("第4棵非空二叉树的高度：%d\n", btree_height(t1));
    printf("/*****第4棵非空二叉树*****/\n\n\n\n");
    /***第4棵非空二叉树（与第5题的第4棵非空二叉树不同）***/

    /***第5棵非空二叉树（只有根结点）***/
    printf("/*****第5棵非空二叉树（只有根结点）*****/\n");
    t_init();
    print_t(t1);
    printf("第5棵非空二叉树的高度：%d\n", btree_height(t1));
    printf("/*****第5棵非空二叉树（只有根结点）*****/\n\n\n\n");
    /***第5棵非空二叉树（只有根结点）***/

    system("pause");
}
/*****主函数*****/